package Real19;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class RSAcrack {
	static long n = 1001733993063167141L;
	static long d = 212353;
	static long c = 20190324;
	static long p,q,k;
	static long e;


	public static void main(String[] args) {
		
		//两个最小的10位数相乘=最小的20-1位数， 两个10位数相乘最大不超过20位(因为达不到21位)
		long sqrtn = 1010000000L;
		long[] ret = zhiyinshu(sqrtn);
		System.out.println("p,q分别为："+ret[0]+","+ret[1]);
		p = ret[0];
		q = ret[1];
			//		p = 891234941;
			//		q = 1123984201;
		k = (p-1)*(q-1);

		long start = System.nanoTime();
		for(long t = 1; ; t++) { //这里迭代暴力求解，迭代的参数一定要选择好，这一题一开始我是想迭代直接求e，但是e的乘数是d 所以e+1增加的步长就是d，而如果迭代求t 则步长为k，二者相差了起码10亿的量级。。前者迭代起来无穷无尽。。。
			
			if( ( ( (t%d)*(k%d) )%d + 1 ) % d == 0) {   //mod和乘除法 是同级别运算 所以要加上()，保证运算顺序；long可能溢出的时候能用mod侵入就用，就像这里一样；如果不能就用大数硬算。。
				System.out.println(t); //174637
				RSAcrack.e = BigInteger.valueOf(t).multiply(BigInteger.valueOf(k)).add(BigInteger.ONE).divide(BigInteger.valueOf(d)).longValue() ;   
				System.out.println("e="+e);   //答案是823816093931522017
				break;
			}
		}
		long end = System.nanoTime();
		System.out.println( "迭代17w次求t的time: " + (end - start) / 1000000000.0 );
				//modPow：pow的mod；即c^e % n 这种形式，执行时间不管参数大小，平均1-2ms左右，如果double不溢出，用math.pow再% 是快很多的，即在迭代里 有把握不用大数运算就不用，如果不迭代用哪个都行；
					//在这个pc上，大数计算一个多项式 一次稳定在1-2ms左右，普通运算计算一个多项式 一次稳定在0.02ms左右，会差几十倍；但迭代起来可能有优化，只进行普通运算的迭代按我的估算能在 1s左右 进行千万级别 的迭代 
		System.out.println("原文为："+ BigInteger.valueOf(c).modPow(BigInteger.valueOf(e), BigInteger.valueOf(n)));  //579706994112328949
	}
//		n=p*q;
//		pq俩质数
//		(d*e) % ((p-1)*(q-1)) == 1
		
//				
//		 (d,(p-1)*(q-1))  互质
//
//		求 c^e % n 
	
	//返回质数 q、p (q*p=n)        先整除了再判断是不是质因数（质-因数），比先判断是不是质数 再判断能不能整除 快的多（因-质数√）；****
	//Version1(采用了注释掉的大数计算):终于跑出来了。。。1.5分钟成功了，注释掉的种种方法都太慢了，出不来结果，某一个版本等了几个小时也没出来结果；
	//Version2(v1是由于记错了long的范围): 换成普通运算只花了 11s；比version1快了10倍
	static long[] zhiyinshu(long sqrtn){  //利用sqrtn估计值 避免了大数不好迭代的尴尬。。这是自己想出来的优化之一；虽然后半部分的重复值迭代不到就有结果了(因为已知肯定有结果)，但是这样就能用long表示迭代次数了；
		
		long[] arr = new long[2];
//		BigInteger[] divideAndRemainder = null;
		
		for (long i = 2; i < sqrtn; i++) {
//			divideAndRemainder = BigInteger.valueOf(RSAcrack.n).divideAndRemainder(BigInteger.valueOf(i)); //TODO:没必要大数计算在这里
			
//			if(divideAndRemainder[1].longValue() == 0) {
			if( n % i == 0) {
				boolean flag = true;
				for(long j = 2; j <= Math.sqrt(i); j++) {  //判断素数的时候，开根号是很关键的，大幅度提高效率；
					if( j == i)   //其实在这里也不会相等
						continue;
				
					if(i % j == 0) {
						flag = false;
						break;   //数据规模很大的时候，break漏掉基本就凉了，结果跑出不来；
					}
				}
				if(flag) {
					arr[0] = i;
					arr[1] = n / i;
					break;
				}
					
			}
		}
		
		return arr;
	}	
		
//	//返回质数 q、p (q*p=n)  
//	//最早的version（质-因数）；                （质-因数）版本； 太慢了，貌似是没有跑出来，因为因数的范围(开根号)比质数范围(200多步长就一定有一个相邻素数)小多了，应该按（因数-质数） 的判断顺序； 
//	static long[] zhiyinshu(long sqrtn){
//		
//		long[] arr = new long[2];
//		BigInteger[] divideAndRemainder = null;
//		
//		for (long i = 2; i < sqrtn; i++) {
//			boolean flag = true;
//			
//			for(long j = 2; j <= Math.sqrt(i); j++) {
//				if( j == i)
//					continue;
//				
//				if(i % j == 0) 
//					flag = false;
//			}
//			
//			if(flag) {
//				divideAndRemainder = RSAcrack.n.divideAndRemainder(BigInteger.valueOf(i));
//				if(divideAndRemainder[1].longValue() == 0) {
//					arr[0] = i;
//					arr[1] = divideAndRemainder[0].longValue();
//					break;
//				}
//			}
//		}
//		
//		return arr;
//	}
	

//	int index = 1;
//	for (int i : zhishu(10000)) {
//		System.out.print(i+",");
//		index++;
//		if(index % 20 == 0)
//			System.out.println();
//	}

	
// ↓↓↓其他测试↓↓↓
	
//	/**
//	 * 测试半天，测试次数极大，还没有出现两组质数相乘结果一样的；      所以碰到这样的条件：n=两个质数的积，那这俩质数是可以直接迭代求出来的；
//	 */
//	ArrayList<Long> zhishu = zhishu(1000);
//	int x = 1;
//	while(x <= 100) {
//		for(int i = 0; i<1000000; i++) {
//			int randomIndex = random(zhishu.size()-1);
//			int randomIndex2 = random(zhishu.size()-1);
//			long a = zhishu.get(randomIndex);
//			long b = zhishu.get(randomIndex2);
//			if (31 * 37 == a * b)
//				System.out.println(a+"*"+b);
//		}
//		x++;
//	}
//}	
	
//	//返回0-n的随机整数
//	static int random(int ceil) {
//		return (int)( Math.random() * (ceil+1) );
//	}
//	
//	//返回0-n的质数列
//	static ArrayList<Long> zhishu(int n){
//		
//		ArrayList<Long> arr = new ArrayList<>();
//		
//		for (int i = 2; i < n; i++) {
//			boolean flag = true;
//			
//			for(int j = 2; j <= Math.sqrt(i); j++) {
//				if( j == i)
//					continue;
//				if(i % j == 0)
//					flag = false;
//			}
//			
//			if(flag)
//				arr.add((long)i);
//			
//		}
//		
//		return arr;
//	}
	
}  //最外层class的括号
